In communications systems, Local Area Networks (LANs) provide communication between a limited number of stations located within a limited geography. A single LAN is known as a LAN segment, and a group of LANs joined together by one or more bridges or routers is known as an extended LAN. A typical LAN segment may connect hundreds of stations over a distance of several kilometers. A bridge or router may be used to connect multiple LAN segments, providing communication between a larger number of stations over a larger area, and preventing excessive local traffic from degrading overall network performance.
The bridge or router monitors the traffic on all the LAN segments to which it is attached, and determines a destination segment (or segments) for each particular frame. To make this determination, the addressing information in the frame is used to locate forwarding information in a forwarding database.
The forwarding information for a specific address is contained in the forwarding entry for that address. Each forwarding entry contains an address field and a forwarding information field. The forwarding information field contains forwarding information for frames containing the address found in the address field.
Add entry and delete entry operations are performed to update the forwarding database as stations are added to and removed from the LAN segments attached to the bridge or router. In many cases, the system manager requests add or delete entry operations through the user interface to the bridge or router.
Add entry operations may also be automatically issued by a learning process within the bridge or router. For example, when a frame is received on LAN segment S, having a station address A in its source address field, and there is no existing forwarding entry with address field equal to A in the forwarding database, a new forwarding entry is added to the forwarding database. The new forwarding entry has an address field equal to A, and forwarding information field indicating that frames received with destination address equal to A should be forwarded onto segment S. In this way, forwarding entries for new stations on the network are added without system manager intervention.
Forwarding entries may also be automatically deleted by an entry aging process within the bridge or router. For example, when a predetermined time period passes where no frame is received with source address equal to A, the aging process may delete the forwarding entry with address field equal to A. In this way, forwarding entries for stations that have been removed from the network are deleted without system manager intervention.
In known bridges, add entry and delete entry operations maintain the forwarding database as an ordered list, sorted on the basis of the address field of the forwarding entries. In these implementations, add entry operations include the steps of:
1) using binary search to find the position within the list for the new entry;
2) moving as many as all the current entries to open up the position for the new entry; and
3) writing the new entry into the ordered list.
A significant drawback in ordered list implementations is that during step 2, a significant amount of processing resources are required to move the existing forwarding entries to accommodate the new entry. In many implementations, the processing resources are shared by multiple processes within the bridge or router. In these implementations, where there is a large forwarding database and frequent add entry operations, this may cause unacceptable performance degradation of processes other than the process performing the add entry operations.
Similarly, in known bridges and routers where the forwarding database is maintained as an ordered list, delete entry operations require significant processing resources to fill in the space created by the deletion. Again, in a worst case, as many as all the remaining forwarding entries in the forwarding table were moved.
A limited improvement is obtainable by making a working copy of the forwarding database before each add entry or delete entry operation, and performing the add entry or delete entry operation on the working copy. The modified working copy is then written over the old forwarding database. Thus, the time the forwarding database is in transition is the time required to write back the working copy. A significant drawback of this approach is that it requires sufficient memory to hold two complete copies of the forwarding database. For large forwarding databases, the required additional memory is impractical, particularly in implementations where memory size is constrained by limited circuit board space.
A further drawback of ordered list forwarding database implementations is the large amount of such shared resources needed to perform add entry and delete entry operations. A worst case add entry operation for an ordered list forwarding database requires lg(n+1) read and compare instructions for the binary search to find the relative position for the new entry, where n is the number of forwarding entries prior to the add, and "lg" is logarithm base 2, as is standard notation in the literature. Move instructions to move the entire forwarding database are also required. For a very large forwarding database, or where add and delete entry operations are frequent, this resource requirement for add entry and delete entry operations may significantly prevent other processes from using the shared resource, and potentially result in their starvation.
A known alternative to ordered list implementations uses a Content Addressable Memory (CAM) to store the forwarding database. In CAM implementations, add entry operations (and similarly delete entry operations), consist of writing the address for which forwarding information is to be added (or deleted) to a first register, writing the forwarding information associated with the address to a second register (in the case of an add entry operation), and writing to a third register requesting the internal logic of the CAM to complete the operation. The number of node microprocessor instructions to perform the operation is therefore less than where the forwarding database is kept in an ordered list.
However, CAM based implementations add significant cost in terms of number of transistors. CAMs require up to a factor of 100 more transistors than non-CAM based implementations. For cost sensitive applications, therefore, a CAM solution is not practical.
For these reasons and others, a new forwarding database management system is required, which reduces the time during which the forwarding database is in transition during add entry and delete entry operations, which does not require additional memory to store a working copy of the forwarding database during add entry and delete entry operations, and which also uses a minimum amount of shared resources, such as microprocessor bandwidth, during add and delete entry operations. Moreover, the new forwarding database management system must be economical, and not rely on costly CAM technology to store the forwarding database.